#include"BinarySearchTree.h"
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;

/** 
 * 创建并返回存放int类型的二叉搜索树
 * 由随机打乱的数组插入生成
 * 可视为平衡二叉搜索树
 */
BinarySearchTree<int>  createbst(int _size=1000)
{
    srand((unsigned int)time(nullptr));
    vector<int> _arr;
    for(int i=0;i<_size;i++)
    {
	_arr.push_back(i);
    }
    ///洗牌算法
    for(int i=_arr.size()-1;i>0;i--)
        {
	    /// index随机下标，用于随机访问数组元素
 	    int index = (int)(rand()%i);
 	    int temp = _arr[index];
 	    _arr[index]=_arr[i];
	    _arr[i]=temp;
        }
     BinarySearchTree<int> _t;
     for(vector<int>::iterator itr=_arr.begin();itr!=_arr.end();++itr)
    {
	_t.insert(*itr);
    }
     return _t;
}

int main(int argc,char *argv[])
{
    clock_t start,end;
    BinarySearchTree<int> t1=createbst(256);
    BinarySearchTree<int> t2=createbst(65536);
    /// 第一次调用函数为冷启动，耗时过久
    start=clock();
    t1.rangesearch(t1.getroot(),101,130);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;

    start=clock();
    t1.rangesearch(t1.getroot(),101,130);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;
    
    start=clock();
    t2.rangesearch(t2.getroot(),201,260);
    cout<<endl;
    end=clock();
    cout<<"the searching spent "<<1000*(double)(end-start)/CLOCKS_PER_SEC<<" ms"<<endl;

    return 0;
}

